// m

// 给定一个只包含数字的字符串，用来表示一个ip地址，返回所有由s构成的有效ip地址，可以按任何顺序返回答案
// 有效ip地址：正好由四个整数（每个整数由0-255的数构成，且不能含有前导0），整数之间用.分割
// 

// 解题思路： 回溯算法
// 使用res存储所有有效ip地址，用point_num表示当前ip地址的.符合个数
// 定义回溯方法，从start_index位置开始遍历字符串
//      1. 如果字符串中添加的.符号数量为3，则判断当前字符串是否为有效ip地址，如果为有效ip地址则加入到res数组中，直接返回
//      2. 然后在[start_index, len(s) - 1]范围内循环遍历，判断[start_index, i]范围所代表的子串是否合法，如果合法
//          1. 则point_num + 1
//          2. 然后在i位置后边增加.符号，继续回溯遍历
//          3. 最后point_num - 1进行回退
//      3. 不符合则直接跳出循环
//      4. 最后返回res

function restoreIpAddress(s) {
    function backstrack(s, start_index, point_num) {
        if (point_num === 3) {
            if (isValid(s, start_index, s.length - 1)) {
                res.push(s)
            }
            return
        }
        for (let i = start_index; i < s.length; i++) {
            if (isValid(s, start_index, i)) {
                point_num += 1
                backstrack(s.substring(0, i + 1) + '.' + s.substring(i + 1), i + 2, point_num)
                point_num -= 1
            } else {
                break
            }
        }
    }
    function isValid(s, start, end) {
        if (start > end) {
            return false
        }
        if (s[start] === '0' && start !== end) {
            return false
        }
        let num = 0
        for (let i = start; i < end + 1; i++) {
            if (s[i] > '9' || s[i] < '0') {
                return false
            }
            num = num * 10 + Number(s[i])
            if (num > 255) {
                return false
            }
        }
        return true
    }
    let res = []
    if (s.length > 12) {
        return res
    }
    backstrack(s, 0, 0)
    return res
}

let s = "25525511135"
console.log(restoreIpAddress(s))